package com.techyuan.algorithm.dp;

/**
 * Created by Administrator on 2017/2/16.
 */
public class matrixChain {
    private static int[][][] matrixChain(int[] p) {
        int n = p.length - 1;
        int[][][] r = new int[2][n][n];
        for (int i = 0; i < n; i++) {
            r[0][i][i] = 0;
        }
        for (int l = 2; l <= n; l++) {//链长
            for (int i = 0; i < n - l + 1; i++) {//第一个矩阵
                int j = i + l - 1;//最后一个矩阵
                r[0][i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {//矩阵切割垫从第一个矩阵开始
                    int q = r[0][i][k] + r[0][k + 1][j] + p[i] * p[k + 1] * p[j + 1];//矩阵连乘的代价
                    if (q < r[0][i][j]) {
                        r[0][i][j] = q;//记录连乘代价
                        r[1][i][j] = k;//记录分割点
                    }
                }
            }
        }
        return r;
    }

    public static void main(String[] args) {
        int[] pArr = {30, 35, 15, 5, 10, 20, 25};
        int[][][] r = matrixChain(pArr);
        System.out.println("结果：" + r[0][0][5]);
        printChain(0, 5, new String[]{"A1", "A2", "A3", "A4", "A5", "A6"}, r[1]);
    }

   private static void printChain(int i, int j, String[] A, int[][] s) {    //递归的方式来把最小乘数的表达式输出

        if (i == j) {
            System.out.print(A[i]);
        } else {
            System.out.print("(");
            printChain(i, s[i][j], A, s);
            printChain(s[i][j] + 1, j, A, s);
            System.out.print(")");
        }
    }
}
